package com.raos.example.redis.networkmodel.lru;

import java.util.HashMap;

/**
 * Redis 缓存清除算法之最少使用清除算法（LRU）
 * 简单实现
 *
 * @author raos
 * @emil 991207823@qq.com
 * @date 2021/7/24 23:04
 **/
public class LRUCache {

    /**
     * 头节点
     */
    private Node head;
    /**
     * 尾节点
     */
    private Node tail;

    /**
     * Node 节点存储容器
     */
    private final HashMap<String, Node> nodeHashMap;
    /**
     * 容量
     */
    private int capacity;

    /**
     * 初始化 LRU 缓存
     * @param capacity 初始容量
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        nodeHashMap = new HashMap<>();
        tail = new Node();
        head = new Node();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 移除节点
     * @param node 需要移除的节点
     */
    private void removeNode(Node node) {
        // 判断是否是末节点（是就将末节点指针前移）
        if (node == tail) {
            tail = tail.prev;
            tail.next = null;
        }
        // 判断是否为首节点（是就将首节点指针后移）
        else if (node == head) {
            head = head.next;
            head.prev = null;
        }
        // 是中间节点（直接插入）
        else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    /**
     * 添加节点到链表头部
     * @param node 需要添加到头部的节点
     */
    private void addNodeToHead(Node node) {
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
    }

    /**
     * 从链表头部移除节点
     * @param node 需移除的节点
     */
    private void moveNodeToHead(Node node) {
        removeNode(node);
        addNodeToHead(node);
    }

    /**
     * 获取key的值
     * @param key
     * @return
     */
    public String get(String key) {
        Node node = nodeHashMap.get(key);
        if (node == null) {
            return null;
        }
        //刷新当前key的位置
        moveNodeToHead(node);
        return node.value;
    }

    /**
     * 添加需存储的 键值对
     * @param key
     * @param value
     */
    public void put(String key, String value) {
        Node node = nodeHashMap.get(key);
        // 判断是否存在，若不存在，则添加到链表并且添加到容器
        if (node == null) {
            // 加入后map长度大于容量，则需要移除老的数据
            if (nodeHashMap.size() >= capacity) {
                //移除尾部节点（tail节点是属于要被淘汰数据）
                removeNode(tail);
                //从hashMap中移除
                nodeHashMap.remove(tail.key);
            }
            node = new Node(key, value);
            nodeHashMap.put(key, node);
            addNodeToHead(node);
        } else {
            node.value = value;
            // 表示最新的数据
            moveNodeToHead(node);
        }
    }

    /**
     * 数据链表数据节点-Node
     */
    class Node {

        private String key;
        private String value;
        /**
         * 前一个链表节点
         */
        Node prev;
        /**
         * 后一个链表节点
         */
        Node next;

        public Node() { }

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

    }

}
